package org.hhchat.leetcode.string;

import java.util.ArrayList;
import java.util.List;

public class code93_medium {
    static class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> list = new ArrayList<String>();
            back(list, s, 0 ,0,"");
            return list;
        }

        public void back(List<String> list, String s, int start, int index, String sb){
            if(index > 4){
                return;
            }
            if (index == 4 && start == s.length()) {
                list.add(sb);
                return;
            }

            for(int i = 1; i < 4; i++) {
                if(start + i > s.length())
                    break;

                String str = s.substring(start, start + i);
                int temp = Integer.valueOf(str);
                if ((str.startsWith("0") && str.length() > 1) || temp > 255) {
                    continue;
                }
                back(list, s, start+i, index+1, sb + str + (index==3?"":"."));
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.restoreIpAddresses("0000"));
    }
}
